package test;

/**
 * 描述：
 *
 * @author hl
 * @version 1.0
 * @date 2020/11/4 8:54
 */
public class KMP {
    public static int getIndexOf(String str1, String str2) {
        if (str1.length() < str2.length()) {
            return -1;
        }
        int[] next = getNextArr(str2);//存放当前元素的上一个元素形成字符串的公共前后缀
        int p1 = 0;
        int p2 = 0;
        while (p1 < str1.length() && p2 < str2.length()) {
            if (str1.charAt(p1) == str2.charAt(p2)) {
                p1++;
                p2++;
                //下面已经是不相等的情况了
            } else if (next[p2] == -1) {
                p1++;
            } else {
                p2 = next[p2];
            }
        }
        return p2 == str2.length() ? p1 - p2 : -1;
    }

    private static int[] getNextArr(String str2) {
        int[] next = new int[str2.length()];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < str2.length()) {
            if (str2.charAt(i - 1) == str2.charAt(cn)) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;//此位置的公共前后缀为0
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndexOf(str, match));
    }
}
